﻿//----------------------------------------------------------
//c LinkList
//12/5/2021 by mky.
//----------------------------------------------------------
#pragma once
#ifndef _LINKELIST_H
#define _LINKELIST_H

//----------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>

//----------------------------------------------------------
#define TRUE 1
#define FALSE 0

//----------------------------------------------------------
typedef int ElemType;//假定线性表的元素类型为整型

//----------------------------------------------------------
//定义节点
typedef struct node {
	ElemType data;
	struct node* pNext;
}LinkListNode;

//----------------------------------------------------------
int main_linkList(void);

//----------------------------------------------------------
///创建带有头节点的链表Init
///函数的返回值是头节点，没有参数
//----------------------------------------------------------
LinkListNode* InitLinkList(void);

//----------------------------------------------------------
///求长度：求顺序表中的元素的个数
///函数的返回值是顺序表的长度，参数pHead：是单链表的头节点
//----------------------------------------------------------
int GetSizeLinkList(LinkListNode* pHead);

//----------------------------------------------------------
///取元素：取给定位置的元素值
///返回值：第i个元素的地址，pHead：头指针，i 待查节点的序号
LinkListNode* GetLinkListNode(LinkListNode* pHead, int pos);

//----------------------------------------------------------
///查元素：查找给定元素值的位置
///返回值：节点的地址，找不到就返回NULL
///pHead:单链表的头指针，objData：是需要匹配的元素值
//----------------------------------------------------------
LinkListNode* LocateLinkList(LinkListNode* pHead, ElemType objData);

//----------------------------------------------------------
///插入元素：在指定的位置插入给定的值
///尾插法建立单链表（将逻辑上的顺序表放入单链表的物理结构当中）
///返回值：链表的头指针，arr:传入的顺序表，length：顺序表的长度
//----------------------------------------------------------
LinkListNode* Create_Rear_LkList(ElemType arr[], int length);

//----------------------------------------------------------
///头插法建立单链表
///返回值：链表的头指针，arr:传入的顺序表，length：顺序表的长度
//----------------------------------------------------------
LinkListNode* Create_Front1_LkList(ElemType arr[], int length);

//----------------------------------------------------------
///头插法2
///返回值：链表的头指针，arr:传入的顺序表，length：顺序表的长度
//----------------------------------------------------------
LinkListNode* Create_Front2_LkList(ElemType arr[], int length);

//----------------------------------------------------------
///头插法建立
///返回值：链表的头指针，arr:传入的顺序表，length：顺序表的长度
//----------------------------------------------------------
LinkListNode* Create_Front3_LkList(ElemType arr[], int length);

//----------------------------------------------------------
///插入元素：在指定的位置插入给定的值
///顺序表：12，33，44，76，89，90（逻辑上的顺序表）=>单链表
///本例中，我们用数组表示这种顺序表
///在指定位置之后插入
///ptr:带插入的元素位置，将在ptr的后继结点中插入，x：插入的值
//----------------------------------------------------------

void Insert_After_LkList(LinkListNode* ptr, ElemType x);

//----------------------------------------------------------
///指定位置之前插入
///pHead:链表的头指针，ptr：带插入的元素位置，x：插入的值
//----------------------------------------------------------
void Insert_Before_LkList(LinkListNode* pHead, LinkListNode* ptr, ElemType x);
void Insert_Before_LkList(LinkListNode* ptr, ElemType x);

//----------------------------------------------------------
///6.删除：删除指定位置的值或者是删除给定的值。
///删除：删除指定位置的值或者是删除给定的值。
///情形一：删除指定节点的后继结点
///情形二：删除第i个节点，假定头节点i=0
///删除返回目标节点的地址，并不涉及到动态空间的回收
///在动态回收空间的要求中，应该遵循的原理是谁污染谁治理
///在顺序表中的删除就是逻辑上的删除，就是说我们的这个节点不再
///存在于当前的顺序表中了
///删除指定节点的后继结点
///返回值是带删除的节点位置
///删除节点：Ptr是需要删除的节点，将删除ptr的后续节点
//----------------------------------------------------------
LinkListNode* Delete_After_LkList(LinkListNode* ptr);

//----------------------------------------------------------
///删除第i个节点，假定头节点i=0
///返回值是带删除的节点位置,pHead:头节点，i是第i个元素
//----------------------------------------------------------
LinkListNode* Delete_i_LkList(LinkListNode* pHead, int i);

//----------------------------------------------------------
///遍历
//----------------------------------------------------------
void ShowLkList(LinkListNode* pHead);

//----------------------------------------------------------
#endif // ! _LINKELIST_H
